#include <vector>

using namespace std;

// 思路： 找到从后往前第一个升序对(i, i+1)，然后在[i+1, end]中找到第一个比nums[i]大的数j，交换nums[i]和nums[j]，然后将[i+1, end]反转
// 时间复杂度O(n)，空间复杂度O(1)
// 具体做法: 从后往前遍历数组，找到第一个满足nums[i] < nums[i+1]的下标i，如果找不到，说明数组是降序排列的，直接反转数组即可
class Solution
{
public:
    void nextPermutation(vector<int> &nums)
    {
        int i;
        for (i = nums.size(); i >= 0; --i)
        {
            if (i + 1 < nums.size() && nums[i] < nums[i + 1])
            {
                for (int j = nums.size() - 1; j > i; --j)
                {
                    if (nums[j] > nums[i])
                    {
                        swap(nums[i], nums[j]);
                        break;
                    }
                }
                break;
            }
        }
        int left = i + 1;
        int right = nums.size() - 1;
        while (left < right)
        {
            swap(nums[left], nums[right]);
            ++left;
            --right;
        }
    }
};